1461B - Find the Spruce - CodeForces Solution


brute force dp implementation *1400

Please click on ads to support us..

C++ Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char arr[510][510];
ll jilu[510][510];
void solve()
{
    int n,m;
    cin>>n>>m;
    memset(jilu,0,sizeof jilu);
    for(int i=1;i<=n;i++)
        cin>>arr[i]+1;
    for(int i=1;i<=n;i++)
    {
        int flag=0,cnt=1;
        for(int j=1;j<=m;j++)
        {
            if(flag==0&&arr[i][j]=='*')
            {
                flag=1;
                jilu[i][j]=++cnt;
            }
            else if(arr[i][j]=='*')
            {
                jilu[i][j]=cnt;
            }
            else
                flag=0;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(arr[i][j]=='*')
            {
                for(int k=1;k<=n;k++)
                {
                    if(i+k>n)
                    {
                        ans+=k;
                        break;
                    }
                    if(j-k<0||j+k>m)
                    {
                        ans+=k;
                        break;
                    }
                    if(jilu[i+k][j-k]!=0&&jilu[i+k][j+k]!=0&&jilu[i+k][j+k]==jilu[i+k][j-k])
                        continue;
                    else
                    {
                        ans+=k;
                        break;
                    }
                }
            }
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    int t;
    cin>>t;
    while(t--)solve();
}

   	 	 	 	 						  									 	


Comments

Submit
0 Comments
More Questions

1626A - Equidistant Letters
977D - Divide by three multiply by two
1654B - Prefix Removals
1654A - Maximum Cake Tastiness
1649A - Game
139A - Petr and Book
1612A - Distance
520A - Pangram
124A - The number of positions
1041A - Heist
901A - Hashing Trees
1283A - Minutes Before the New Year
1654D - Potion Brewing Class
1107B - Digital root
25A - IQ test
785A - Anton and Polyhedrons
1542B - Plus and Multiply
306A - Candies
1651C - Fault-tolerant Network
870A - Search for Pretty Integers
1174A - Ehab Fails to Be Thanos
1169A - Circle Metro
780C - Andryusha and Colored Balloons
1153A - Serval and Bus
1487C - Minimum Ties
1136A - Nastya Is Reading a Book
1353B - Two Arrays And Swaps
1490E - Accidental Victory
1335A - Candies and Two Sisters
96B - Lucky Numbers (easy)